#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode dummy(0), *pre, *cur;
            pre = &dummy;
            cur = head;
            while(cur) {
                if (!cur->next || (cur->next && cur->val != cur->next->val)) {
                    pre->next = cur;
                    pre = pre->next;
                    cur = cur->next;
                    continue;
                }
                while(cur->next && cur->val == cur->next->val) 
                    cur = cur->next;
                if (!cur->next) pre->next = NULL;
                cur = cur->next;
            }
            return dummy.next; 
        }
};
//add better clean code.
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) return head;
        ListNode Dummy(0), *h = &Dummy;
        while(head) {
            h->next = head;
            h = h->next;
            head = head->next;
            while (head && head->val == h->val) head = head->next;
        }   
        h->next = NULL;
        return Dummy.next; 
    }


ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);

    return node;
}

//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    int data[] = {1,4,4,4,4,4,5,6,7};
    ListNode *list1;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    ListNode *list = mySolution.deleteDuplicates(list1);
    while(list) {
        cout << list->val << " ";
        list= list->next;
    }
    cout << endl;

    cout << "-----------------Test 2--------------------" << endl;
    int data1[] = {1,1,1,1,1,1,4,5,6,7,7,7,7};
    ListNode *list2;
    list2 = newList(data1, 0, sizeof(data1)/sizeof(int));
    list = mySolution.deleteDuplicates(list2);
    while(list) {
        cout << list->val << " ";
        list= list->next;
    }
    cout << endl;


}
